home *** CD-ROM | disk | FTP | other *** search
open in: 
MacOS 8.1
|
Win98
|
DOS
view JSON data
|
view as text
This file was processed as: Mailbox/MIME Entity
(archive/mbox).
You can browse this item here: polyclip.code
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 100%
| dexvert
| Mailbox/MIME Entity (archive/mbox)
| magic
| Supported |
| 1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
| 100%
| file
| Mailbox text, 1st line "From ucsdhub!hp-sdd!hplabs!hao!noao!arizona!naucse!sbw Fri Mar 27 07:24:37 PST 1987"
| default
| |
| 99%
| file
| C source, ASCII text
| default
| |
| 100%
| checkBytes
| Printable ASCII
| default
| |
| 100%
| perlTextCheck
| Likely Text (Perl)
| default
| |
| 100%
| siegfried
| x-fmt/111 Plain Text File
| default
| |
| 100%
| detectItEasy
| Format: plain text[LF]
| default (weak)
| |
| 100%
| xdgMime
| application/mbox
| default
|
|
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 46 72 6f 6d 20 75 63 73 | 64 68 75 62 21 68 70 2d |From ucs|dhub!hp-|
|00000010| 73 64 64 21 68 70 6c 61 | 62 73 21 68 61 6f 21 6e |sdd!hpla|bs!hao!n|
|00000020| 6f 61 6f 21 61 72 69 7a | 6f 6e 61 21 6e 61 75 63 |oao!ariz|ona!nauc|
|00000030| 73 65 21 73 62 77 20 46 | 72 69 20 4d 61 72 20 32 |se!sbw F|ri Mar 2|
|00000040| 37 20 30 37 3a 32 34 3a | 33 37 20 50 53 54 20 31 |7 07:24:|37 PST 1|
|00000050| 39 38 37 0a 0a 54 68 65 | 20 66 6f 6c 6c 6f 77 69 |987..The| followi|
|00000060| 6e 67 20 43 20 66 75 6e | 63 74 69 6f 6e 73 20 61 |ng C fun|ctions a|
|00000070| 72 65 20 74 77 6f 20 76 | 65 72 73 69 6f 6e 73 20 |re two v|ersions |
|00000080| 6f 66 20 74 68 65 20 4c | 69 61 6e 67 2d 42 61 72 |of the L|iang-Bar|
|00000090| 73 6b 79 0a 70 6f 6c 79 | 67 6f 6e 20 63 6c 69 70 |sky.poly|gon clip|
|000000a0| 70 69 6e 67 20 61 6c 67 | 6f 72 69 74 68 6d 2e 20 |ping alg|orithm. |
|000000b0| 20 54 68 65 20 66 69 72 | 73 74 20 69 73 20 64 69 | The fir|st is di|
|000000c0| 72 65 63 74 6c 79 20 66 | 72 6f 6d 20 74 68 65 69 |rectly f|rom thei|
|000000d0| 72 0a 70 61 70 65 72 20 | 69 6e 20 43 41 43 4d 20 |r.paper |in CACM |
|000000e0| 28 61 6e 64 20 74 68 65 | 20 63 6f 72 72 69 67 65 |(and the| corrige|
|000000f0| 6e 64 61 20 74 68 61 74 | 20 66 6f 6c 6c 6f 77 65 |nda that| followe|
|00000100| 64 29 2e 20 20 54 68 65 | 20 73 65 63 6f 6e 64 0a |d). The| second.|
|00000110| 69 73 20 73 6c 69 67 68 | 74 6c 79 20 6d 6f 64 69 |is sligh|tly modi|
|00000120| 66 69 65 64 20 61 6e 64 | 20 73 65 65 6d 73 20 74 |fied and| seems t|
|00000130| 6f 20 72 75 6e 20 61 62 | 6f 75 74 20 36 25 20 71 |o run ab|out 6% q|
|00000140| 75 69 63 6b 65 72 20 28 | 61 73 73 75 6d 69 6e 67 |uicker (|assuming|
|00000150| 0a 66 6c 6f 61 74 69 6e | 67 20 70 6f 69 6e 74 20 |.floatin|g point |
|00000160| 68 61 72 64 77 61 72 65 | 29 2e 0a 0a 23 5f 5f 5f |hardware|)...#___|
|00000170| 5f 5f 5f 5f 5f 5f 5f 5f | 63 75 74 20 6d 61 72 6b |________|cut mark|
|00000180| 0a 0a 2f 2a 20 4c 69 61 | 6e 67 2d 42 61 72 73 6b |../* Lia|ng-Barsk|
|00000190| 79 20 50 6f 6c 79 67 6f | 6e 20 43 6c 69 70 70 69 |y Polygo|n Clippi|
|000001a0| 6e 67 20 5b 43 41 43 4d | 2c 20 56 6f 6c 20 32 36 |ng [CACM|, Vol 26|
|000001b0| 20 28 4e 6f 76 2c 20 31 | 39 38 33 29 5d 0a 20 2a | (Nov, 1|983)]. *|
|000001c0| 20 20 20 20 28 77 69 74 | 68 20 63 6f 72 72 65 63 | (wit|h correc|
|000001d0| 74 69 6f 6e 73 20 66 72 | 6f 6d 20 5b 43 41 43 4d |tions fr|om [CACM|
|000001e0| 20 28 41 70 72 69 6c 2c | 20 31 39 38 34 29 5d 29 | (April,| 1984)])|
|000001f0| 0a 20 2a 2f 0a 0a 2f 2a | 20 20 20 4e 6f 74 65 20 |. */../*| Note |
|00000200| 74 68 61 74 20 74 68 69 | 73 20 61 73 73 75 6d 65 |that thi|s assume|
|00000210| 73 20 74 68 65 20 6c 61 | 73 74 20 70 6f 69 6e 74 |s the la|st point|
|00000220| 20 3d 3d 20 74 68 65 20 | 66 69 72 73 74 20 69 6e | == the |first in|
|00000230| 20 74 68 65 0a 20 2a 20 | 20 20 20 70 6f 6c 79 67 | the. * | polyg|
|00000240| 6f 6e 20 72 65 70 72 65 | 73 65 6e 74 61 74 69 6f |on repre|sentatio|
|00000250| 6e 20 74 68 65 20 63 6f | 64 65 20 69 6e 20 74 68 |n the co|de in th|
|00000260| 65 20 61 72 74 69 63 6c | 65 20 61 64 64 73 20 74 |e articl|e adds t|
|00000270| 68 65 0a 20 2a 20 20 20 | 20 6c 61 73 74 20 70 6f |he. * | last po|
|00000280| 69 6e 74 20 69 6e 20 61 | 74 20 74 68 65 20 73 74 |int in a|t the st|
|00000290| 61 72 74 20 6f 66 20 74 | 68 65 20 61 6c 67 6f 72 |art of t|he algor|
|000002a0| 69 74 68 6d 20 28 70 72 | 6f 62 61 62 6c 79 0a 20 |ithm (pr|obably. |
|000002b0| 2a 20 20 20 20 61 20 62 | 65 74 74 65 72 20 61 70 |* a b|etter ap|
|000002c0| 70 72 6f 61 63 68 29 2e | 0a 20 2a 2f 0a 0a 09 2f |proach).|. */.../|
|000002d0| 2a 20 54 68 65 20 66 6f | 6c 6c 6f 77 69 6e 67 20 |* The fo|llowing |
|000002e0| 69 6e 63 6c 75 64 65 20 | 62 72 69 6e 67 73 20 69 |include |brings i|
|000002f0| 6e 20 73 6f 6d 65 20 6d | 61 63 72 6f 20 64 65 66 |n some m|acro def|
|00000300| 69 6e 69 74 69 6f 6e 73 | 0a 09 20 2a 20 66 6f 72 |initions|.. * for|
|00000310| 20 61 63 63 65 73 73 69 | 6e 67 20 69 6e 66 6f 72 | accessi|ng infor|
|00000320| 6d 61 74 69 6f 6e 20 61 | 62 6f 75 74 20 61 20 70 |mation a|bout a p|
|00000330| 6f 6c 79 67 6f 6e 3a 0a | 09 20 2a 0a 09 20 2a 20 |olygon:.|. *.. * |
|00000340| 20 20 4e 50 4e 54 53 28 | 29 20 20 69 73 20 74 68 | NPNTS(|) is th|
|00000350| 65 20 6e 75 6d 62 65 72 | 20 6f 66 20 76 65 72 74 |e number| of vert|
|00000360| 69 63 65 73 20 69 6e 20 | 74 68 65 20 70 6f 6c 79 |ices in |the poly|
|00000370| 67 6f 6e 0a 09 20 2a 20 | 20 20 20 20 20 20 20 20 |gon.. * | |
|00000380| 20 20 20 28 63 6f 75 6e | 74 69 6e 67 20 66 69 72 | (coun|ting fir|
|00000390| 73 74 20 70 6f 69 6e 74 | 20 74 77 69 63 65 29 0a |st point| twice).|
|000003a0| 20 20 20 20 20 20 20 20 | 20 2a 0a 20 20 20 20 20 | | *. |
|000003b0| 20 20 20 20 2a 20 20 20 | 47 45 54 50 4e 54 28 29 | * |GETPNT()|
|000003c0| 20 61 63 63 65 73 73 65 | 73 20 74 68 65 20 73 70 | accesse|s the sp|
|000003d0| 65 63 69 66 69 65 64 20 | 70 6f 69 6e 74 20 6f 75 |ecified |point ou|
|000003e0| 74 20 6f 66 20 74 68 65 | 0a 09 20 2a 20 20 20 20 |t of the|.. * |
|000003f0| 09 20 20 20 20 20 20 70 | 6f 6c 79 67 6f 6e 2e 0a |. p|olygon..|
|00000400| 09 20 2a 0a 09 20 2a 20 | 20 20 58 43 4f 4f 52 44 |. *.. * | XCOORD|
|00000410| 2f 59 43 4f 4f 52 44 28 | 29 20 61 63 63 65 73 73 |/YCOORD(|) access|
|00000420| 20 74 68 65 20 78 28 79 | 29 2d 63 6f 6f 72 64 69 | the x(y|)-coordi|
|00000430| 6e 61 74 65 20 69 6e 20 | 61 20 70 6f 69 6e 74 0a |nate in |a point.|
|00000440| 09 20 2a 0a 09 20 2a 20 | 4d 61 63 72 6f 73 20 77 |. *.. * |Macros w|
|00000450| 65 72 65 20 75 73 65 64 | 20 62 65 63 61 75 73 65 |ere used| because|
|00000460| 20 74 68 69 73 20 63 6f | 64 65 20 6d 75 73 74 20 | this co|de must |
|00000470| 75 6c 74 69 6d 61 74 65 | 6c 79 20 74 69 65 0a 09 |ultimate|ly tie..|
|00000480| 20 2a 20 20 69 6e 74 6f | 20 6d 79 20 77 69 66 65 | * into| my wife|
|00000490| 27 73 20 61 6e 69 6d 61 | 74 69 6f 6e 20 70 61 63 |'s anima|tion pac|
|000004a0| 6b 61 67 65 2c 20 61 6e | 64 20 49 20 64 6f 6e 27 |kage, an|d I don'|
|000004b0| 74 20 6b 6e 6f 77 0a 09 | 20 2a 20 20 68 6f 77 20 |t know..| * how |
|000004c0| 73 68 65 20 69 73 20 67 | 6f 69 6e 67 20 74 6f 20 |she is g|oing to |
|000004d0| 72 65 70 72 65 73 65 6e | 74 20 70 6f 6c 79 67 6f |represen|t polygo|
|000004e0| 6e 73 20 79 65 74 2e 0a | 09 20 2a 2f 0a 0a 23 20 |ns yet..|. */..# |
|000004f0| 69 6e 63 6c 75 64 65 20 | 22 70 6c 6e 2e 68 22 0a |include |"pln.h".|
|00000500| 0a 23 20 64 65 66 69 6e | 65 20 49 4e 46 49 4e 49 |.# defin|e INFINI|
|00000510| 54 59 09 28 31 2e 30 65 | 2b 33 30 29 0a 0a 09 2f |TY.(1.0e|+30).../|
|00000520| 2a 20 61 64 64 20 61 20 | 6e 65 77 20 76 65 72 74 |* add a |new vert|
|00000530| 65 78 20 69 6e 74 6f 20 | 74 68 65 20 6f 75 74 70 |ex into |the outp|
|00000540| 75 74 20 70 6f 6c 79 67 | 6f 6e 20 2a 2f 0a 0a 23 |ut polyg|on */..#|
|00000550| 20 64 65 66 69 6e 65 20 | 61 64 64 28 78 2c 79 29 | define |add(x,y)|
|00000560| 20 7b 5c 0a 20 20 20 20 | 20 20 20 20 20 20 20 20 | {\. | |
|00000570| 20 20 20 20 20 20 20 58 | 43 4f 4f 52 44 28 47 45 | X|COORD(GE|
|00000580| 54 50 4e 54 28 6e 70 6f | 6c 79 2c 6e 70 6e 74 29 |TPNT(npo|ly,npnt)|
|00000590| 29 20 3d 20 78 3b 5c 0a | 20 20 20 20 20 20 20 20 |) = x;\.| |
|000005a0| 20 20 20 20 20 20 20 20 | 20 20 20 59 43 4f 4f 52 | | YCOOR|
|000005b0| 44 28 47 45 54 50 4e 54 | 28 6e 70 6f 6c 79 2c 6e |D(GETPNT|(npoly,n|
|000005c0| 70 6e 74 29 29 20 3d 20 | 79 3b 5c 0a 20 20 20 20 |pnt)) = |y;\. |
|000005d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 2b | | +|
|000005e0| 2b 6e 70 6e 74 3b 5c 0a | 20 20 20 20 20 20 20 20 |+npnt;\.| |
|000005f0| 20 20 20 20 20 20 20 20 | 20 20 7d 0a 0a 09 2f 2a | | }.../*|
|00000600| 20 77 69 6e 64 6f 77 20 | 62 6f 75 6e 64 73 20 28 | window |bounds (|
|00000610| 78 6c 65 66 74 2c 79 62 | 6f 74 74 6f 6d 29 2c 20 |xleft,yb|ottom), |
|00000620| 28 78 72 69 67 68 74 2c | 79 74 6f 70 29 20 2a 2f |(xright,|ytop) */|
|00000630| 0a 65 78 74 65 72 6e 20 | 66 6c 6f 61 74 20 77 78 |.extern |float wx|
|00000640| 31 2c 77 79 31 2c 20 20 | 77 78 32 2c 77 79 32 3b |1,wy1, |wx2,wy2;|
|00000650| 0a 0a 09 2f 2a 20 54 68 | 65 20 4c 69 61 6e 67 2d |.../* Th|e Liang-|
|00000660| 42 61 72 73 6b 79 20 50 | 6f 6c 79 67 6f 6e 20 43 |Barsky P|olygon C|
|00000670| 6c 69 70 70 69 6e 67 20 | 41 6c 67 6f 72 69 74 68 |lipping |Algorith|
|00000680| 6d 20 2a 2f 0a 66 63 6c | 69 70 28 6f 70 6f 6c 79 |m */.fcl|ip(opoly|
|00000690| 2c 6e 70 6f 6c 79 29 0a | 20 20 20 50 4c 4e 20 2a |,npoly).| PLN *|
|000006a0| 6f 70 6f 6c 79 2c 20 2a | 6e 70 6f 6c 79 3b 0a 0a |opoly, *|npoly;..|
|000006b0| 20 20 20 7b 0a 20 20 20 | 72 65 67 69 73 74 65 72 | {. |register|
|000006c0| 20 69 6e 74 20 69 2c 20 | 6e 70 6e 74 3b 0a 20 20 | int i, |npnt;. |
|000006d0| 20 66 6c 6f 61 74 20 64 | 65 6c 74 61 78 2c 20 64 | float d|eltax, d|
|000006e0| 65 6c 74 61 79 2c 20 78 | 69 6e 2c 78 6f 75 74 2c |eltay, x|in,xout,|
|000006f0| 20 20 79 69 6e 2c 79 6f | 75 74 3b 0a 20 20 20 66 | yin,yo|ut;. f|
|00000700| 6c 6f 61 74 20 74 69 6e | 78 2c 74 69 6e 79 2c 20 |loat tin|x,tiny, |
|00000710| 20 74 6f 75 74 78 2c 74 | 6f 75 74 79 2c 20 20 74 | toutx,t|outy, t|
|00000720| 69 6e 31 2c 20 74 69 6e | 32 2c 20 20 74 6f 75 74 |in1, tin|2, tout|
|00000730| 31 2c 74 6f 75 74 32 3b | 0a 20 20 20 66 6c 6f 61 |1,tout2;|. floa|
|00000740| 74 20 78 31 2c 79 31 2c | 20 78 32 2c 79 32 3b 0a |t x1,y1,| x2,y2;.|
|00000750| 20 20 20 0a 20 20 20 6e | 70 6e 74 20 3d 20 30 3b | . n|pnt = 0;|
|00000760| 0a 0a 20 20 20 66 6f 72 | 20 28 69 20 3d 20 30 3b |.. for| (i = 0;|
|00000770| 20 69 20 3c 20 4e 50 4e | 54 53 28 6f 70 6f 6c 79 | i < NPN|TS(opoly|
|00000780| 29 2d 31 3b 20 2b 2b 69 | 29 20 7b 0a 0a 20 20 20 |)-1; ++i|) {.. |
|00000790| 20 20 20 78 31 20 3d 20 | 58 43 4f 4f 52 44 28 47 | x1 = |XCOORD(G|
|000007a0| 45 54 50 4e 54 28 6f 70 | 6f 6c 79 2c 69 29 29 3b |ETPNT(op|oly,i));|
|000007b0| 0a 20 20 20 20 20 20 79 | 31 20 3d 20 59 43 4f 4f |. y|1 = YCOO|
|000007c0| 52 44 28 47 45 54 50 4e | 54 28 6f 70 6f 6c 79 2c |RD(GETPN|T(opoly,|
|000007d0| 69 29 29 3b 0a 20 20 20 | 20 20 20 78 32 20 3d 20 |i));. | x2 = |
|000007e0| 58 43 4f 4f 52 44 28 47 | 45 54 50 4e 54 28 6f 70 |XCOORD(G|ETPNT(op|
|000007f0| 6f 6c 79 2c 69 2b 31 29 | 29 3b 0a 20 20 20 20 20 |oly,i+1)|);. |
|00000800| 20 79 32 20 3d 20 59 43 | 4f 4f 52 44 28 47 45 54 | y2 = YC|OORD(GET|
|00000810| 50 4e 54 28 6f 70 6f 6c | 79 2c 69 2b 31 29 29 3b |PNT(opol|y,i+1));|
|00000820| 0a 0a 20 20 20 20 20 20 | 64 65 6c 74 61 78 20 3d |.. |deltax =|
|00000830| 20 78 32 2d 78 31 3b 0a | 20 20 20 20 20 20 64 65 | x2-x1;.| de|
|00000840| 6c 74 61 79 20 3d 20 79 | 32 2d 79 31 3b 0a 0a 20 |ltay = y|2-y1;.. |
|00000850| 20 20 20 20 20 69 66 20 | 28 64 65 6c 74 61 78 20 | if |(deltax |
|00000860| 3e 20 30 20 7c 7c 20 28 | 64 65 6c 74 61 78 20 3d |> 0 || (|deltax =|
|00000870| 3d 20 30 20 26 26 20 78 | 31 3e 77 78 32 29 29 20 |= 0 && x|1>wx2)) |
|00000880| 7b 20 2f 2a 20 20 70 6f | 69 6e 74 73 20 74 6f 20 |{ /* po|ints to |
|00000890| 72 69 67 68 74 20 2a 2f | 0a 20 20 20 20 20 20 20 |right */|. |
|000008a0| 20 20 78 69 6e 20 3d 20 | 77 78 31 3b 0a 20 20 20 | xin = |wx1;. |
|000008b0| 20 20 20 20 20 20 78 6f | 75 74 20 3d 20 77 78 32 | xo|ut = wx2|
|000008c0| 3b 0a 20 20 20 20 20 20 | 20 20 20 7d 0a 20 20 20 |;. | }. |
|000008d0| 20 20 20 65 6c 73 65 20 | 7b 0a 20 20 20 20 20 20 | else |{. |
|000008e0| 20 20 20 78 69 6e 20 3d | 20 77 78 32 3b 0a 20 20 | xin =| wx2;. |
|000008f0| 20 20 20 20 20 20 20 78 | 6f 75 74 20 3d 20 77 78 | x|out = wx|
|00000900| 31 3b 0a 20 20 20 20 20 | 20 20 20 20 7d 0a 20 20 |1;. | }. |
|00000910| 20 20 20 20 69 66 20 28 | 64 65 6c 74 61 79 20 3e | if (|deltay >|
|00000920| 20 30 20 7c 7c 20 28 64 | 65 6c 74 61 79 20 3d 3d | 0 || (d|eltay ==|
|00000930| 20 30 20 26 26 20 79 31 | 3e 77 79 32 29 29 20 7b | 0 && y1|>wy2)) {|
|00000940| 20 2f 2a 20 20 70 6f 69 | 6e 74 73 20 75 70 20 2a | /* poi|nts up *|
|00000950| 2f 0a 20 20 20 20 20 20 | 20 20 20 79 69 6e 20 3d |/. | yin =|
|00000960| 20 77 79 31 3b 0a 20 20 | 20 20 20 20 20 20 20 79 | wy1;. | y|
|00000970| 6f 75 74 20 3d 20 77 79 | 32 3b 0a 20 20 20 20 20 |out = wy|2;. |
|00000980| 20 20 20 20 7d 0a 20 20 | 20 20 20 20 65 6c 73 65 | }. | else|
|00000990| 20 7b 0a 20 20 20 20 20 | 20 20 20 20 79 69 6e 20 | {. | yin |
|000009a0| 3d 20 77 79 32 3b 0a 20 | 20 20 20 20 20 20 20 20 |= wy2;. | |
|000009b0| 79 6f 75 74 20 3d 20 77 | 79 31 3b 0a 20 20 20 20 |yout = w|y1;. |
|000009c0| 20 20 20 20 20 7d 0a 0a | 20 20 20 20 20 20 74 69 | }..| ti|
|000009d0| 6e 78 20 3d 20 28 64 65 | 6c 74 61 78 20 21 3d 20 |nx = (de|ltax != |
|000009e0| 30 29 20 3f 20 28 28 78 | 69 6e 20 2d 20 78 31 29 |0) ? ((x|in - x1)|
|000009f0| 2f 64 65 6c 74 61 78 29 | 20 3a 20 2d 49 4e 46 49 |/deltax)| : -INFI|
|00000a00| 4e 49 54 59 20 3b 0a 20 | 20 20 20 20 20 74 69 6e |NITY ;. | tin|
|00000a10| 79 20 3d 20 28 64 65 6c | 74 61 79 20 21 3d 20 30 |y = (del|tay != 0|
|00000a20| 29 20 3f 20 28 28 79 69 | 6e 20 2d 20 79 31 29 2f |) ? ((yi|n - y1)/|
|00000a30| 64 65 6c 74 61 79 29 20 | 3a 20 2d 49 4e 46 49 4e |deltay) |: -INFIN|
|00000a40| 49 54 59 20 3b 0a 20 20 | 20 0a 20 20 20 20 20 20 |ITY ;. | . |
|00000a50| 69 66 20 28 74 69 6e 78 | 20 3c 20 74 69 6e 79 29 |if (tinx| < tiny)|
|00000a60| 20 7b 09 2f 2a 20 68 69 | 74 73 20 78 20 66 69 72 | {./* hi|ts x fir|
|00000a70| 73 74 20 2a 2f 0a 20 20 | 20 20 20 20 20 20 20 74 |st */. | t|
|00000a80| 69 6e 31 20 3d 20 74 69 | 6e 78 3b 0a 20 20 20 20 |in1 = ti|nx;. |
|00000a90| 20 20 20 20 20 74 69 6e | 32 20 3d 20 74 69 6e 79 | tin|2 = tiny|
|00000aa0| 3b 0a 20 20 20 20 20 20 | 20 20 20 7d 0a 20 20 20 |;. | }. |
|00000ab0| 20 20 20 65 6c 73 65 09 | 09 09 2f 2a 20 68 69 74 | else.|../* hit|
|00000ac0| 73 20 79 20 66 69 72 73 | 74 20 2a 2f 0a 20 20 20 |s y firs|t */. |
|00000ad0| 20 20 20 20 20 20 7b 0a | 20 20 20 20 20 20 20 20 | {.| |
|00000ae0| 20 74 69 6e 31 20 3d 20 | 74 69 6e 79 3b 0a 20 20 | tin1 = |tiny;. |
|00000af0| 20 20 20 20 20 20 20 74 | 69 6e 32 20 3d 20 74 69 | t|in2 = ti|
|00000b00| 6e 78 3b 0a 20 20 20 20 | 20 20 20 20 20 7d 0a 0a |nx;. | }..|
|00000b10| 20 20 20 20 20 20 69 66 | 20 28 31 20 3e 3d 20 74 | if| (1 >= t|
|00000b20| 69 6e 31 29 20 7b 0a 20 | 20 20 20 20 20 20 20 20 |in1) {. | |
|00000b30| 69 66 20 28 30 20 3c 20 | 74 69 6e 31 29 20 7b 0a |if (0 < |tin1) {.|
|00000b40| 20 20 20 20 20 20 20 20 | 20 20 20 20 61 64 64 28 | | add(|
|00000b50| 78 69 6e 2c 79 69 6e 29 | 3b 0a 20 20 20 20 20 20 |xin,yin)|;. |
|00000b60| 20 20 20 20 20 20 7d 0a | 20 20 20 20 20 20 20 20 | }.| |
|00000b70| 20 69 66 20 28 31 20 3e | 3d 20 74 69 6e 32 29 20 | if (1 >|= tin2) |
|00000b80| 7b 0a 09 20 20 20 20 69 | 66 20 28 64 65 6c 74 61 |{.. i|f (delta|
|00000b90| 78 20 21 3d 20 30 29 20 | 74 6f 75 74 78 20 3d 20 |x != 0) |toutx = |
|00000ba0| 28 78 6f 75 74 2d 78 31 | 29 2f 64 65 6c 74 61 78 |(xout-x1|)/deltax|
|00000bb0| 3b 0a 09 20 20 20 20 65 | 6c 73 65 20 7b 0a 20 20 |;.. e|lse {. |
|00000bc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 69 66 20 | | if |
|00000bd0| 28 77 78 31 20 3c 3d 20 | 78 31 20 26 26 20 78 31 |(wx1 <= |x1 && x1|
|00000be0| 20 3c 3d 20 77 78 32 29 | 20 74 6f 75 74 78 20 3d | <= wx2)| toutx =|
|00000bf0| 20 49 4e 46 49 4e 49 54 | 59 3b 0a 20 20 20 20 20 | INFINIT|Y;. |
|00000c00| 20 20 20 20 20 20 20 20 | 20 20 65 6c 73 65 20 20 | | else |
|00000c10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000c20| 20 20 20 20 20 20 74 6f | 75 74 78 20 3d 20 2d 49 | to|utx = -I|
|00000c30| 4e 46 49 4e 49 54 59 3b | 0a 09 20 20 20 20 20 20 |NFINITY;|.. |
|00000c40| 20 7d 0a 09 20 20 20 20 | 69 66 20 28 64 65 6c 74 | }.. |if (delt|
|00000c50| 61 79 20 21 3d 20 30 29 | 20 74 6f 75 74 79 20 3d |ay != 0)| touty =|
|00000c60| 20 28 79 6f 75 74 2d 79 | 31 29 2f 64 65 6c 74 61 | (yout-y|1)/delta|
|00000c70| 79 3b 0a 09 20 20 20 20 | 65 6c 73 65 20 7b 0a 20 |y;.. |else {. |
|00000c80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 69 66 | | if|
|00000c90| 20 28 77 79 31 20 3c 3d | 20 79 31 20 26 26 20 79 | (wy1 <=| y1 && y|
|00000ca0| 31 20 3c 3d 20 77 79 32 | 29 20 74 6f 75 74 79 20 |1 <= wy2|) touty |
|00000cb0| 3d 20 49 4e 46 49 4e 49 | 54 59 3b 0a 20 20 20 20 |= INFINI|TY;. |
|00000cc0| 20 20 20 20 20 20 20 20 | 20 20 20 65 6c 73 65 20 | | else |
|00000cd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000ce0| 20 20 20 20 20 20 20 74 | 6f 75 74 79 20 3d 20 2d | t|outy = -|
|00000cf0| 49 4e 46 49 4e 49 54 59 | 3b 0a 09 20 20 20 20 20 |INFINITY|;.. |
|00000d00| 20 20 7d 0a 0a 09 20 20 | 20 20 74 6f 75 74 31 20 | }... | tout1 |
|00000d10| 3d 20 28 74 6f 75 74 78 | 20 3c 20 74 6f 75 74 79 |= (toutx| < touty|
|00000d20| 29 20 3f 20 74 6f 75 74 | 78 20 3a 20 74 6f 75 74 |) ? tout|x : tout|
|00000d30| 79 20 3b 0a 20 20 20 0a | 20 20 20 20 20 20 20 20 |y ;. .| |
|00000d40| 20 20 20 20 69 66 20 28 | 30 20 3c 20 74 69 6e 32 | if (|0 < tin2|
|00000d50| 20 7c 7c 20 30 20 3c 20 | 74 6f 75 74 31 29 20 7b | || 0 < |tout1) {|
|00000d60| 0a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|00000d70| 69 66 20 28 74 69 6e 32 | 20 3c 3d 20 74 6f 75 74 |if (tin2| <= tout|
|00000d80| 31 29 20 7b 0a 20 20 20 | 20 20 20 20 20 20 20 20 |1) {. | |
|00000d90| 20 20 20 20 20 20 20 69 | 66 20 28 30 20 3c 20 74 | i|f (0 < t|
|00000da0| 69 6e 32 29 20 7b 0a 20 | 20 20 20 20 20 20 20 20 |in2) {. | |
|00000db0| 20 20 20 20 20 20 20 20 | 20 20 20 20 69 66 20 28 | | if (|
|00000dc0| 74 69 6e 78 20 3e 20 74 | 69 6e 79 29 20 7b 0a 20 |tinx > t|iny) {. |
|00000dd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000de0| 20 20 20 20 20 20 20 61 | 64 64 20 28 78 69 6e 2c | a|dd (xin,|
|00000df0| 20 79 31 2b 74 69 6e 78 | 2a 64 65 6c 74 61 79 29 | y1+tinx|*deltay)|
|00000e00| 3b 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |;. | |
|00000e10| 20 20 20 20 20 20 20 20 | 20 20 7d 0a 20 20 20 20 | | }. |
|00000e20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000e30| 20 65 6c 73 65 20 7b 0a | 20 20 20 20 20 20 20 20 | else {.| |
|00000e40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000e50| 61 64 64 20 28 78 31 20 | 2b 20 74 69 6e 79 2a 64 |add (x1 |+ tiny*d|
|00000e60| 65 6c 74 61 78 2c 20 79 | 69 6e 29 3b 0a 20 20 20 |eltax, y|in);. |
|00000e70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000e80| 20 20 20 20 20 7d 0a 20 | 20 20 20 20 20 20 20 20 | }. | |
|00000e90| 20 20 20 20 20 20 20 20 | 20 20 20 20 7d 0a 20 20 | | }. |
|00000ea0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000eb0| 69 66 20 28 31 20 3e 20 | 74 6f 75 74 31 29 20 7b |if (1 > |tout1) {|
|00000ec0| 0a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|00000ed0| 20 20 20 20 20 20 69 66 | 20 28 74 6f 75 74 78 20 | if| (toutx |
|00000ee0| 3c 20 74 6f 75 74 79 29 | 20 7b 0a 20 20 20 20 20 |< touty)| {. |
|00000ef0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000f00| 20 20 20 61 64 64 20 28 | 78 6f 75 74 2c 20 79 31 | add (|xout, y1|
|00000f10| 2b 74 6f 75 74 78 2a 64 | 65 6c 74 61 79 29 3b 0a |+toutx*d|eltay);.|
|00000f20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000f30| 20 20 20 20 20 20 20 20 | 7d 0a 20 20 20 20 20 20 | |}. |
|00000f40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 65 | | e|
|00000f50| 6c 73 65 20 7b 0a 20 20 | 20 20 20 20 20 20 20 20 |lse {. | |
|00000f60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 61 64 | | ad|
|00000f70| 64 20 28 78 31 20 2b 20 | 74 6f 75 74 79 2a 64 65 |d (x1 + |touty*de|
|00000f80| 6c 74 61 78 2c 20 79 6f | 75 74 29 3b 0a 20 20 20 |ltax, yo|ut);. |
|00000f90| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000fa0| 20 20 20 20 20 7d 0a 20 | 20 20 20 20 20 20 20 20 | }. | |
|00000fb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 7d 0a 20 20 | | }. |
|00000fc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000fd0| 65 6c 73 65 20 7b 0a 20 | 20 20 20 20 20 20 20 20 |else {. | |
|00000fe0| 20 20 20 20 20 20 20 20 | 20 20 20 20 61 64 64 20 | | add |
|00000ff0| 28 78 32 2c 79 32 29 3b | 0a 20 20 20 20 20 20 20 |(x2,y2);|. |
|00001000| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 7d 0a | | }.|
|00001010| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001020| 20 20 7d 0a 20 20 20 20 | 20 20 20 20 20 20 20 20 | }. | |
|00001030| 20 20 20 65 6c 73 65 20 | 7b 0a 20 20 20 20 20 20 | else |{. |
|00001040| 20 20 20 20 20 20 20 20 | 20 20 20 20 69 66 20 28 | | if (|
|00001050| 74 69 6e 78 20 3e 20 74 | 69 6e 79 29 20 7b 0a 20 |tinx > t|iny) {. |
|00001060| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001070| 20 20 20 20 61 64 64 20 | 28 78 69 6e 2c 20 79 6f | add |(xin, yo|
|00001080| 75 74 29 3b 0a 20 20 20 | 20 20 20 20 20 20 20 20 |ut);. | |
|00001090| 20 20 20 20 20 20 20 20 | 20 20 7d 0a 20 20 20 20 | | }. |
|000010a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 65 6c | | el|
|000010b0| 73 65 20 7b 0a 20 20 20 | 20 20 20 20 20 20 20 20 |se {. | |
|000010c0| 20 20 20 20 20 20 20 20 | 20 20 61 64 64 20 28 78 | | add (x|
|000010d0| 6f 75 74 2c 20 79 69 6e | 29 3b 0a 20 20 20 20 20 |out, yin|);. |
|000010e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000010f0| 7d 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |}. | |
|00001100| 20 20 20 20 7d 0a 20 20 | 20 20 20 20 20 20 20 20 | }. | |
|00001110| 20 20 20 20 20 7d 0a 20 | 20 20 20 20 20 20 20 20 | }. | |
|00001120| 20 20 20 7d 0a 20 20 20 | 20 20 20 20 20 20 7d 0a | }. | }.|
|00001130| 20 20 20 20 20 20 7d 0a | 0a 20 20 20 69 66 20 28 | }.|. if (|
|00001140| 6e 70 6e 74 29 20 7b 0a | 20 20 20 20 20 20 61 64 |npnt) {.| ad|
|00001150| 64 28 58 43 4f 4f 52 44 | 28 47 45 54 50 4e 54 28 |d(XCOORD|(GETPNT(|
|00001160| 6e 70 6f 6c 79 2c 30 29 | 29 2c 59 43 4f 4f 52 44 |npoly,0)|),YCOORD|
|00001170| 28 47 45 54 50 4e 54 28 | 6e 70 6f 6c 79 2c 30 29 |(GETPNT(|npoly,0)|
|00001180| 29 29 3b 0a 20 20 20 20 | 20 20 7d 0a 20 20 20 4e |));. | }. N|
|00001190| 50 4e 54 53 28 6e 70 6f | 6c 79 29 20 3d 20 6e 70 |PNTS(npo|ly) = np|
|000011a0| 6e 74 3b 0a 20 20 20 7d | 0a 0a 23 5f 5f 5f 5f 5f |nt;. }|..#_____|
|000011b0| 5f 5f 5f 5f 5f 5f 20 63 | 75 74 20 6d 61 72 6b 0a |______ c|ut mark.|
|000011c0| 0a 2f 2a 20 4d 6f 64 69 | 66 69 65 64 20 4c 69 61 |./* Modi|fied Lia|
|000011d0| 6e 67 2d 42 61 72 73 6b | 79 20 50 6f 6c 79 67 6f |ng-Barsk|y Polygo|
|000011e0| 6e 20 43 6c 69 70 70 69 | 6e 67 20 5b 43 41 43 4d |n Clippi|ng [CACM|
|000011f0| 2c 20 56 6f 6c 20 32 36 | 20 28 4e 6f 76 2c 20 31 |, Vol 26| (Nov, 1|
|00001200| 39 38 33 29 5d 20 2a 2f | 0a 0a 2f 2a 20 73 65 65 |983)] */|../* see|
|00001210| 20 74 68 65 20 63 6f 6d | 6d 65 6e 74 73 20 61 74 | the com|ments at|
|00001220| 20 74 68 65 20 73 74 61 | 72 74 20 6f 66 20 74 68 | the sta|rt of th|
|00001230| 65 20 75 6e 6d 6f 64 69 | 66 69 65 64 20 76 65 72 |e unmodi|fied ver|
|00001240| 73 69 6f 6e 20 66 6f 72 | 20 6d 6f 72 65 0a 20 2a |sion for| more. *|
|00001250| 20 64 65 74 61 69 6c 73 | 2e 0a 20 2a 2f 0a 0a 23 | details|.. */..#|
|00001260| 20 69 6e 63 6c 75 64 65 | 20 22 70 6c 6e 2e 68 22 | include| "pln.h"|
|00001270| 0a 0a 23 20 64 65 66 69 | 6e 65 20 49 4e 46 49 4e |..# defi|ne INFIN|
|00001280| 49 54 59 09 28 31 2e 30 | 65 2b 33 30 29 0a 23 20 |ITY.(1.0|e+30).# |
|00001290| 64 65 66 69 6e 65 20 4e | 45 41 52 5a 45 52 4f 09 |define N|EARZERO.|
|000012a0| 28 31 2e 30 65 2d 33 30 | 29 09 2f 2a 20 31 2f 49 |(1.0e-30|)./* 1/I|
|000012b0| 4e 46 49 4e 49 54 59 20 | 2a 2f 0a 0a 23 20 64 65 |NFINITY |*/..# de|
|000012c0| 66 69 6e 65 20 61 64 64 | 28 78 2c 79 29 20 7b 5c |fine add|(x,y) {\|
|000012d0| 0a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|000012e0| 20 20 20 20 58 43 4f 4f | 52 44 28 47 45 54 50 4e | XCOO|RD(GETPN|
|000012f0| 54 28 6e 70 6f 6c 79 2c | 6e 70 6e 74 29 29 20 3d |T(npoly,|npnt)) =|
|00001300| 20 78 3b 5c 0a 20 20 20 | 20 20 20 20 20 20 20 20 | x;\. | |
|00001310| 20 20 20 20 20 20 20 20 | 59 43 4f 4f 52 44 28 47 | |YCOORD(G|
|00001320| 45 54 50 4e 54 28 6e 70 | 6f 6c 79 2c 6e 70 6e 74 |ETPNT(np|oly,npnt|
|00001330| 29 29 20 3d 20 79 3b 5c | 0a 20 20 20 20 20 20 20 |)) = y;\|. |
|00001340| 20 20 20 20 20 20 20 20 | 20 20 20 20 2b 2b 6e 70 | | ++np|
|00001350| 6e 74 3b 5c 0a 20 20 20 | 20 20 20 20 20 20 20 20 |nt;\. | |
|00001360| 20 20 20 20 20 20 20 7d | 0a 0a 65 78 74 65 72 6e | }|..extern|
|00001370| 20 66 6c 6f 61 74 20 77 | 78 31 2c 77 79 31 2c 20 | float w|x1,wy1, |
|00001380| 20 77 78 32 2c 77 79 32 | 3b 09 2f 2a 20 77 69 6e | wx2,wy2|;./* win|
|00001390| 64 6f 77 20 62 6f 75 6e | 64 61 72 69 65 73 20 2a |dow boun|daries *|
|000013a0| 2f 0a 0a 66 63 6c 69 70 | 28 6f 70 6f 6c 79 2c 6e |/..fclip|(opoly,n|
|000013b0| 70 6f 6c 79 29 0a 20 20 | 20 50 4c 4e 20 2a 6f 70 |poly). | PLN *op|
|000013c0| 6f 6c 79 2c 20 2a 6e 70 | 6f 6c 79 3b 0a 0a 20 20 |oly, *np|oly;.. |
|000013d0| 20 7b 0a 20 20 20 72 65 | 67 69 73 74 65 72 20 69 | {. re|gister i|
|000013e0| 6e 74 20 69 2c 20 6e 70 | 6e 74 3b 0a 20 20 20 66 |nt i, np|nt;. f|
|000013f0| 6c 6f 61 74 20 64 65 6c | 74 61 78 2c 20 64 65 6c |loat del|tax, del|
|00001400| 74 61 79 2c 20 78 69 6e | 2c 78 6f 75 74 2c 20 20 |tay, xin|,xout, |
|00001410| 79 69 6e 2c 79 6f 75 74 | 3b 0a 20 20 20 66 6c 6f |yin,yout|;. flo|
|00001420| 61 74 20 74 69 6e 78 2c | 74 69 6e 79 2c 20 20 74 |at tinx,|tiny, t|
|00001430| 6f 75 74 78 2c 74 6f 75 | 74 79 2c 20 20 74 69 6e |outx,tou|ty, tin|
|00001440| 31 2c 20 74 69 6e 32 2c | 20 20 74 6f 75 74 31 2c |1, tin2,| tout1,|
|00001450| 74 6f 75 74 32 3b 0a 20 | 20 20 66 6c 6f 61 74 20 |tout2;. | float |
|00001460| 78 31 2c 79 31 2c 20 78 | 32 2c 79 32 3b 0a 20 20 |x1,y1, x|2,y2;. |
|00001470| 20 0a 20 20 20 6e 70 6e | 74 20 3d 20 30 3b 0a 0a | . npn|t = 0;..|
|00001480| 20 20 20 66 6f 72 20 28 | 69 20 3d 20 30 3b 20 69 | for (|i = 0; i|
|00001490| 20 3c 20 4e 50 4e 54 53 | 28 6f 70 6f 6c 79 29 2d | < NPNTS|(opoly)-|
|000014a0| 31 3b 20 2b 2b 69 29 20 | 7b 0a 0a 20 20 20 20 20 |1; ++i) |{.. |
|000014b0| 20 78 31 20 3d 20 58 43 | 4f 4f 52 44 28 47 45 54 | x1 = XC|OORD(GET|
|000014c0| 50 4e 54 28 6f 70 6f 6c | 79 2c 69 29 29 3b 0a 20 |PNT(opol|y,i));. |
|000014d0| 20 20 20 20 20 79 31 20 | 3d 20 59 43 4f 4f 52 44 | y1 |= YCOORD|
|000014e0| 28 47 45 54 50 4e 54 28 | 6f 70 6f 6c 79 2c 69 29 |(GETPNT(|opoly,i)|
|000014f0| 29 3b 0a 20 20 20 20 20 | 20 78 32 20 3d 20 58 43 |);. | x2 = XC|
|00001500| 4f 4f 52 44 28 47 45 54 | 50 4e 54 28 6f 70 6f 6c |OORD(GET|PNT(opol|
|00001510| 79 2c 69 2b 31 29 29 3b | 0a 20 20 20 20 20 20 79 |y,i+1));|. y|
|00001520| 32 20 3d 20 59 43 4f 4f | 52 44 28 47 45 54 50 4e |2 = YCOO|RD(GETPN|
|00001530| 54 28 6f 70 6f 6c 79 2c | 69 2b 31 29 29 3b 0a 0a |T(opoly,|i+1));..|
|00001540| 20 20 20 20 20 20 64 65 | 6c 74 61 78 20 3d 20 78 | de|ltax = x|
|00001550| 32 2d 78 31 3b 0a 20 20 | 20 20 20 20 69 66 20 28 |2-x1;. | if (|
|00001560| 64 65 6c 74 61 78 20 3d | 3d 20 30 29 20 7b 20 2f |deltax =|= 0) { /|
|00001570| 2a 20 62 75 6d 70 20 6f | 66 66 20 6f 66 20 74 68 |* bump o|ff of th|
|00001580| 65 20 76 65 72 74 69 63 | 61 6c 20 2a 2f 0a 20 20 |e vertic|al */. |
|00001590| 20 20 20 20 20 20 20 64 | 65 6c 74 61 78 20 3d 20 | d|eltax = |
|000015a0| 28 78 31 20 3e 20 77 78 | 31 29 20 3f 20 2d 4e 45 |(x1 > wx|1) ? -NE|
|000015b0| 41 52 5a 45 52 4f 20 3a | 20 4e 45 41 52 5a 45 52 |ARZERO :| NEARZER|
|000015c0| 4f 20 3b 0a 20 20 20 20 | 20 20 20 20 20 7d 0a 20 |O ;. | }. |
|000015d0| 20 20 20 20 20 64 65 6c | 74 61 79 20 3d 20 79 32 | del|tay = y2|
|000015e0| 2d 79 31 3b 0a 20 20 20 | 20 20 20 69 66 20 28 64 |-y1;. | if (d|
|000015f0| 65 6c 74 61 79 20 3d 3d | 20 30 29 20 7b 20 2f 2a |eltay ==| 0) { /*|
|00001600| 20 62 75 6d 70 20 6f 66 | 66 20 6f 66 20 74 68 65 | bump of|f of the|
|00001610| 20 68 6f 72 69 7a 6f 6e | 74 61 6c 20 2a 2f 0a 20 | horizon|tal */. |
|00001620| 20 20 20 20 20 20 20 20 | 64 65 6c 74 61 79 20 3d | |deltay =|
|00001630| 20 28 79 31 20 3e 20 77 | 79 31 29 20 3f 20 2d 4e | (y1 > w|y1) ? -N|
|00001640| 45 41 52 5a 45 52 4f 20 | 3a 20 4e 45 41 52 5a 45 |EARZERO |: NEARZE|
|00001650| 52 4f 20 3b 0a 20 20 20 | 20 20 20 20 20 20 7d 0a |RO ;. | }.|
|00001660| 0a 20 20 20 20 20 20 69 | 66 20 28 64 65 6c 74 61 |. i|f (delta|
|00001670| 78 20 3e 20 30 29 20 7b | 09 09 2f 2a 20 20 70 6f |x > 0) {|../* po|
|00001680| 69 6e 74 73 20 74 6f 20 | 72 69 67 68 74 20 2a 2f |ints to |right */|
|00001690| 0a 20 20 20 20 20 20 20 | 20 20 78 69 6e 20 3d 20 |. | xin = |
|000016a0| 77 78 31 3b 0a 20 20 20 | 20 20 20 20 20 20 78 6f |wx1;. | xo|
|000016b0| 75 74 20 3d 20 77 78 32 | 3b 0a 20 20 20 20 20 20 |ut = wx2|;. |
|000016c0| 20 20 20 7d 0a 20 20 20 | 20 20 20 65 6c 73 65 20 | }. | else |
|000016d0| 7b 0a 20 20 20 20 20 20 | 20 20 20 78 69 6e 20 3d |{. | xin =|
|000016e0| 20 77 78 32 3b 0a 20 20 | 20 20 20 20 20 20 20 78 | wx2;. | x|
|000016f0| 6f 75 74 20 3d 20 77 78 | 31 3b 0a 20 20 20 20 20 |out = wx|1;. |
|00001700| 20 20 20 20 7d 0a 20 20 | 20 20 20 20 69 66 20 28 | }. | if (|
|00001710| 64 65 6c 74 61 79 20 3e | 20 30 29 20 7b 09 09 2f |deltay >| 0) {../|
|00001720| 2a 20 20 70 6f 69 6e 74 | 73 20 75 70 20 2a 2f 0a |* point|s up */.|
|00001730| 20 20 20 20 20 20 20 20 | 20 79 69 6e 20 3d 20 77 | | yin = w|
|00001740| 79 31 3b 0a 20 20 20 20 | 20 20 20 20 20 79 6f 75 |y1;. | you|
|00001750| 74 20 3d 20 77 79 32 3b | 0a 20 20 20 20 20 20 20 |t = wy2;|. |
|00001760| 20 20 7d 0a 20 20 20 20 | 20 20 65 6c 73 65 20 7b | }. | else {|
|00001770| 0a 20 20 20 20 20 20 20 | 20 20 79 69 6e 20 3d 20 |. | yin = |
|00001780| 77 79 32 3b 0a 20 20 20 | 20 20 20 20 20 20 79 6f |wy2;. | yo|
|00001790| 75 74 20 3d 20 77 79 31 | 3b 0a 20 20 20 20 20 20 |ut = wy1|;. |
|000017a0| 20 20 20 7d 0a 0a 20 20 | 20 20 20 20 74 69 6e 78 | }.. | tinx|
|000017b0| 20 3d 20 28 78 69 6e 20 | 2d 20 78 31 29 2f 64 65 | = (xin |- x1)/de|
|000017c0| 6c 74 61 78 3b 0a 20 20 | 20 20 20 20 74 69 6e 79 |ltax;. | tiny|
|000017d0| 20 3d 20 28 79 69 6e 20 | 2d 20 79 31 29 2f 64 65 | = (yin |- y1)/de|
|000017e0| 6c 74 61 79 3b 0a 20 20 | 20 0a 20 20 20 20 20 20 |ltay;. | . |
|000017f0| 69 66 20 28 74 69 6e 78 | 20 3c 20 74 69 6e 79 29 |if (tinx| < tiny)|
|00001800| 20 7b 09 2f 2a 20 68 69 | 74 73 20 78 20 66 69 72 | {./* hi|ts x fir|
|00001810| 73 74 20 2a 2f 0a 20 20 | 20 20 20 20 20 20 20 74 |st */. | t|
|00001820| 69 6e 31 20 3d 20 74 69 | 6e 78 3b 0a 20 20 20 20 |in1 = ti|nx;. |
|00001830| 20 20 20 20 20 74 69 6e | 32 20 3d 20 74 69 6e 79 | tin|2 = tiny|
|00001840| 3b 0a 20 20 20 20 20 20 | 20 20 20 7d 0a 20 20 20 |;. | }. |
|00001850| 20 20 20 65 6c 73 65 09 | 09 09 2f 2a 20 68 69 74 | else.|../* hit|
|00001860| 73 20 79 20 66 69 72 73 | 74 20 2a 2f 0a 20 20 20 |s y firs|t */. |
|00001870| 20 20 20 20 20 20 7b 0a | 20 20 20 20 20 20 20 20 | {.| |
|00001880| 20 74 69 6e 31 20 3d 20 | 74 69 6e 79 3b 0a 20 20 | tin1 = |tiny;. |
|00001890| 20 20 20 20 20 20 20 74 | 69 6e 32 20 3d 20 74 69 | t|in2 = ti|
|000018a0| 6e 78 3b 0a 20 20 20 20 | 20 20 20 20 20 7d 0a 0a |nx;. | }..|
|000018b0| 20 20 20 20 20 20 69 66 | 20 28 31 20 3e 3d 20 74 | if| (1 >= t|
|000018c0| 69 6e 31 29 20 7b 0a 20 | 20 20 20 20 20 20 20 20 |in1) {. | |
|000018d0| 69 66 20 28 30 20 3c 20 | 74 69 6e 31 29 20 7b 0a |if (0 < |tin1) {.|
|000018e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 61 64 64 28 | | add(|
|000018f0| 78 69 6e 2c 79 69 6e 29 | 3b 0a 20 20 20 20 20 20 |xin,yin)|;. |
|00001900| 20 20 20 20 20 20 7d 0a | 20 20 20 20 20 20 20 20 | }.| |
|00001910| 20 69 66 20 28 31 20 3e | 3d 20 74 69 6e 32 29 20 | if (1 >|= tin2) |
|00001920| 7b 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 74 6f |{. | to|
|00001930| 75 74 78 20 3d 20 28 78 | 6f 75 74 20 2d 20 78 31 |utx = (x|out - x1|
|00001940| 29 2f 64 65 6c 74 61 78 | 3b 0a 20 20 20 20 20 20 |)/deltax|;. |
|00001950| 20 20 20 20 20 20 74 6f | 75 74 79 20 3d 20 28 79 | to|uty = (y|
|00001960| 6f 75 74 20 2d 20 79 31 | 29 2f 64 65 6c 74 61 79 |out - y1|)/deltay|
|00001970| 3b 0a 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 74 |;.. | t|
|00001980| 6f 75 74 31 20 3d 20 28 | 74 6f 75 74 78 20 3c 20 |out1 = (|toutx < |
|00001990| 74 6f 75 74 79 29 20 3f | 20 74 6f 75 74 78 20 3a |touty) ?| toutx :|
|000019a0| 20 74 6f 75 74 79 20 3b | 0a 20 20 20 0a 20 20 20 | touty ;|. . |
|000019b0| 20 20 20 20 20 20 20 20 | 20 69 66 20 28 30 20 3c | | if (0 <|
|000019c0| 20 74 69 6e 32 20 7c 7c | 20 30 20 3c 20 74 6f 75 | tin2 ||| 0 < tou|
|000019d0| 74 31 29 20 7b 0a 20 20 | 20 20 20 20 20 20 20 20 |t1) {. | |
|000019e0| 20 20 20 20 20 69 66 20 | 28 74 69 6e 32 20 3c 3d | if |(tin2 <=|
|000019f0| 20 74 6f 75 74 31 29 20 | 7b 0a 20 20 20 20 20 20 | tout1) |{. |
|00001a00| 20 20 20 20 20 20 20 20 | 20 20 20 20 69 66 20 28 | | if (|
|00001a10| 30 20 3c 20 74 69 6e 32 | 29 20 7b 0a 20 20 20 20 |0 < tin2|) {. |
|00001a20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001a30| 20 69 66 20 28 74 69 6e | 78 20 3e 20 74 69 6e 79 | if (tin|x > tiny|
|00001a40| 29 20 7b 0a 20 20 20 20 | 20 20 20 20 20 20 20 20 |) {. | |
|00001a50| 20 20 20 20 20 20 20 20 | 20 20 20 20 61 64 64 20 | | add |
|00001a60| 28 78 69 6e 2c 20 79 31 | 2b 74 69 6e 78 2a 64 65 |(xin, y1|+tinx*de|
|00001a70| 6c 74 61 79 29 3b 0a 20 | 20 20 20 20 20 20 20 20 |ltay);. | |
|00001a80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 7d | | }|
|00001a90| 0a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|00001aa0| 20 20 20 20 20 20 65 6c | 73 65 20 7b 0a 20 20 20 | el|se {. |
|00001ab0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001ac0| 20 20 20 20 20 61 64 64 | 20 28 78 31 20 2b 20 74 | add| (x1 + t|
|00001ad0| 69 6e 79 2a 64 65 6c 74 | 61 78 2c 20 79 69 6e 29 |iny*delt|ax, yin)|
|00001ae0| 3b 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |;. | |
|00001af0| 20 20 20 20 20 20 20 20 | 20 20 7d 0a 20 20 20 20 | | }. |
|00001b00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001b10| 20 7d 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | }. | |
|00001b20| 20 20 20 20 20 69 66 20 | 28 31 20 3e 20 74 6f 75 | if |(1 > tou|
|00001b30| 74 31 29 20 7b 0a 20 20 | 20 20 20 20 20 20 20 20 |t1) {. | |
|00001b40| 20 20 20 20 20 20 20 20 | 20 20 20 69 66 20 28 74 | | if (t|
|00001b50| 6f 75 74 78 20 3c 20 74 | 6f 75 74 79 29 20 7b 0a |outx < t|outy) {.|
|00001b60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001b70| 20 20 20 20 20 20 20 20 | 61 64 64 20 28 78 6f 75 | |add (xou|
|00001b80| 74 2c 20 79 31 2b 74 6f | 75 74 78 2a 64 65 6c 74 |t, y1+to|utx*delt|
|00001b90| 61 79 29 3b 0a 20 20 20 | 20 20 20 20 20 20 20 20 |ay);. | |
|00001ba0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 7d 0a 20 | | }. |
|00001bb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001bc0| 20 20 20 20 65 6c 73 65 | 20 7b 0a 20 20 20 20 20 | else| {. |
|00001bd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001be0| 20 20 20 61 64 64 20 28 | 78 31 20 2b 20 74 6f 75 | add (|x1 + tou|
|00001bf0| 74 79 2a 64 65 6c 74 61 | 78 2c 20 79 6f 75 74 29 |ty*delta|x, yout)|
|00001c00| 3b 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |;. | |
|00001c10| 20 20 20 20 20 20 20 20 | 20 20 7d 0a 20 20 20 20 | | }. |
|00001c20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001c30| 20 7d 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | }. | |
|00001c40| 20 20 20 20 20 65 6c 73 | 65 20 7b 0a 20 20 20 20 | els|e {. |
|00001c50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001c60| 20 61 64 64 20 28 78 32 | 2c 79 32 29 3b 0a 20 20 | add (x2|,y2);. |
|00001c70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001c80| 20 20 20 7d 0a 20 20 20 | 20 20 20 20 20 20 20 20 | }. | |
|00001c90| 20 20 20 20 20 20 20 7d | 0a 20 20 20 20 20 20 20 | }|. |
|00001ca0| 20 20 20 20 20 20 20 20 | 65 6c 73 65 20 7b 0a 20 | |else {. |
|00001cb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001cc0| 20 69 66 20 28 74 69 6e | 78 20 3e 20 74 69 6e 79 | if (tin|x > tiny|
|00001cd0| 29 20 7b 0a 20 20 20 20 | 20 20 20 20 20 20 20 20 |) {. | |
|00001ce0| 20 20 20 20 20 20 20 20 | 20 61 64 64 20 28 78 69 | | add (xi|
|00001cf0| 6e 2c 20 79 6f 75 74 29 | 3b 0a 20 20 20 20 20 20 |n, yout)|;. |
|00001d00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 7d | | }|
|00001d10| 0a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|00001d20| 20 20 20 65 6c 73 65 20 | 7b 0a 20 20 20 20 20 20 | else |{. |
|00001d30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 61 | | a|
|00001d40| 64 64 20 28 78 6f 75 74 | 2c 20 79 69 6e 29 3b 0a |dd (xout|, yin);.|
|00001d50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001d60| 20 20 20 20 20 7d 0a 20 | 20 20 20 20 20 20 20 20 | }. | |
|00001d70| 20 20 20 20 20 20 20 20 | 20 7d 0a 20 20 20 20 20 | | }. |
|00001d80| 20 20 20 20 20 20 20 20 | 20 20 7d 0a 20 20 20 20 | | }. |
|00001d90| 20 20 20 20 20 20 20 20 | 7d 0a 20 20 20 20 20 20 | |}. |
|00001da0| 20 20 20 7d 0a 20 20 20 | 20 20 20 7d 0a 0a 20 20 | }. | }.. |
|00001db0| 20 69 66 20 28 6e 70 6e | 74 29 20 7b 0a 20 20 20 | if (npn|t) {. |
|00001dc0| 20 20 20 61 64 64 28 58 | 43 4f 4f 52 44 28 47 45 | add(X|COORD(GE|
|00001dd0| 54 50 4e 54 28 6e 70 6f | 6c 79 2c 30 29 29 2c 59 |TPNT(npo|ly,0)),Y|
|00001de0| 43 4f 4f 52 44 28 47 45 | 54 50 4e 54 28 6e 70 6f |COORD(GE|TPNT(npo|
|00001df0| 6c 79 2c 30 29 29 29 3b | 0a 20 20 20 20 20 20 7d |ly,0)));|. }|
|00001e00| 0a 20 20 20 4e 50 4e 54 | 53 28 6e 70 6f 6c 79 29 |. NPNT|S(npoly)|
|00001e10| 20 3d 20 6e 70 6e 74 3b | 0a 20 20 20 7d 0a 0a 23 | = npnt;|. }..#|
|00001e20| 5f 5f 5f 5f 5f 5f 5f 5f | 5f 20 63 75 74 20 6d 61 |________|_ cut ma|
|00001e30| 72 6b 0a 0a 0a 2d 53 74 | 65 76 65 20 57 61 6d 70 |rk...-St|eve Wamp|
|00001e40| 6c 65 72 0a 7b 2e 2e 2e | 7d 21 61 72 69 7a 6f 6e |ler.{...|}!arizon|
|00001e50| 61 21 6e 61 75 63 73 65 | 21 73 62 77 0a 0a 0a |a!naucse|!sbw... |
+--------+-------------------------+-------------------------+--------+--------+
